\defmodule{F2wCycleBasedPolyLCG}

This class creates a point set based upon
a linear congruential sequence in the finite field
 $\latex{\mathbb{F}}\html{\mathbf{F}}_{2^w}[z]/P(z)$.
The recurrence is
$$
q_n(z) = z^s q_{n-1}(z)\ \mod P(z)
$$
where $P(z)\in \latex{\mathbb{F}}\html{\mathbf{F}}_{2^w}[z]$ has degree $r$ and
$q_n(z) = q_{n,1} z^{r-1} + \cdots + q_{n,r} \in
 \latex{\mathbb{F}}\html{\mathbf{F}}_{2^w}[z]/P(z)$.
The parameter $s$ is
called the stepping parameter of the recurrence.
The polynomial $P(z)$ is not necessarily the characteristic polynomial
of this recurrence, but it can still be used to store the parameters of
 the recurrence.
In the implementation, it is stored in an object of the class
 \externalclass{umontreal.iro.lecuyer.hups}{F2wStructure}.  See the description
of this class for more details on how the polynomial
is stored.


Let $\mathbf{x} = (x^{(0)}, \ldots, x^{(p-1)}) \in
 \latex{\mathbb{F}}\html{\mathbf{F}}_{2}^p$ be a $p$-bit vector.
Let us define the function $\phi(\mathbf{x}) =
\sum_{i=1}^{p} 2^{-i} x^{(i-1)}$.
The point set in $t$ dimensions produced by this class is
$$
\{ (\phi(\mathbf{y}_0),\phi(\mathbf{y}_1),\ldots,\phi(\mathbf{y}_{t-1}):
 (\mathbf{q}_{0,1},\ldots,\mathbf{q}_{0,r-1})\in
 \latex{\mathbb{F}}\html{\mathbf{F}}_{2}^{rw}\}
$$
where $\mathbf{y}_n = (\mathbf{q}_{n,1},\ldots,\mathbf{q}_{n,r})$,
 $\mathbf{q}_{n,i}$
 is the representation of $q_{n,i}$ under the polynomial basis of
$\latex{\mathbb{F}}\html{\mathbf{F}}_{2^w}$ over
 $\latex{\mathbb{F}}\html{\mathbf{F}}_2$.

\bigskip\hrule\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{code}
\begin{hide}
/*
 * Class:        F2wCycleBasedPolyLCG
 * Description:  point set based upon a linear congruential sequence in a
                 finite field
 * Environment:  Java
 * Software:     SSJ 
 * Copyright (C) 2001  Pierre L'Ecuyer and Universite de Montreal
 * Organization: DIRO, Universite de Montreal
 * @author       
 * @since

 * SSJ is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License (GPL) as published by the
 * Free Software Foundation, either version 3 of the License, or
 * any later version.

 * SSJ is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * A copy of the GNU General Public License is available at
   <a href="http://www.gnu.org/licenses">GPL licence site</a>.
 */
\end{hide}
package umontreal.iro.lecuyer.hups; \begin{hide}
import umontreal.iro.lecuyer.util.PrintfFormat;
import umontreal.iro.lecuyer.rng.*;
import cern.colt.list.*;
\end{hide}


public class F2wCycleBasedPolyLCG extends CycleBasedPointSetBase2 \begin{hide} {

   private F2wStructure param;
\end{hide}\end{code}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection*{Constructors}
\begin{code}

   public F2wCycleBasedPolyLCG (int w, int r, int modQ, int step, int nbcoeff,
                                int coeff[], int nocoeff[]) \begin{hide}
    /**
     * Constructs and stores the set of cycles for an LCG with
     *    modulus <SPAN CLASS="MATH"><I>n</I></SPAN> and multiplier <SPAN CLASS="MATH"><I>a</I></SPAN>.
     *   If pgcd<SPAN CLASS="MATH">(<I>a</I>, <I>n</I>) = 1</SPAN>, this constructs a full-period LCG which has two
     *   cycles, one containing 0 and one, the LCG period.
     *
     * @param n required number of points and modulo of the LCG
     *
     *    @param a generator <SPAN CLASS="MATH"><I>a</I></SPAN> of the LCG
     *
     *
     */
   {
      param = new F2wStructure (w, r, modQ, step, nbcoeff, coeff, nocoeff);
      numBits = param.numBits;
      normFactor = param.normFactor;
      EpsilonHalf = param.EpsilonHalf;
      fillCyclesPolyLCG ();
   }\end{hide}
\end{code}
 \begin{tabb}
 Constructs a point set with $2^{rw}$ points.  See the description of the class
 \externalclass{umontreal.iro.lecuyer.hups}{F2wStructure}
 for the meaning of the parameters.
 \end{tabb}
\begin{code}

   public F2wCycleBasedPolyLCG (String filename, int no) \begin{hide}
   {
      param = new F2wStructure (filename, no);
      numBits = param.numBits;
      normFactor = param.normFactor;
      fillCyclesPolyLCG ();
   }\end{hide}
\end{code}
 \begin{tabb}
   Constructs a point set after reading its parameters from
   file \texttt{filename}; the parameters are located at line numbered \texttt{no}
   of \texttt{filename}. The available files are listed in the description of class
\externalclass{umontreal.iro.lecuyer.hups}{F2wStructure}.
 \end{tabb}
\begin{code}
\begin{hide}

   public String toString ()
   {
       String s = "F2wCycleBasedPolyLCG:" + PrintfFormat.NEWLINE;
       return s + param.toString ();
   }

   private void fillCyclesPolyLCG ()
   {
      int n = 1 << param.getLog2N();
      int i;
      int mask1 = (1 << (31 - param.r * param.w)) - 1;
      int mask2 = ~mask1;
      RandomStream random = new MRG32k3a();
      IntArrayList c;             // Array used to store the current cycle.
      int currentState;           // The state currently visited.

      boolean stateVisited[] = new boolean[n];
      // Indicates which states have been visited so far.
      for (i = 0; i < n; i++)
         stateVisited[i] = false;
      int startState = 0;  // First state of the cycle currently considered.
      numPoints = 0;
      while (startState < n) {
         stateVisited[startState] = true;
         c = new IntArrayList ();
         param.state = startState << param.S;
         c.add (param.state);
         // c.add ((state & mask2) | (mask1 &
         // (random.nextInt(0,2147483647))));
         param.output = param.F2wPolyLCG ();
         // Warning: watch for overflow !!!
         while (param.state != (startState << param.S)) {
            stateVisited[param.state >> param.S] = true;
            // c.add ((param.state&mask2) | (mask1 &
            // (random.nextInt(0,2147483647))));
            c.add (param.state);
            param.output = param.F2wPolyLCG ();
         }
         addCycle (c);
         for (i = startState + 1; i < n; i++)
            if (stateVisited[i] == false)
               break;
         startState = i;
      }
   }
}
\end{hide}
\end{code}
